1. Field of the Disclosure
This disclosure relates generally to concurrent accesses to shared objects, and more particularly to a system and method for tracking references to shared objects using a reference tracking data structure that includes byte-addressable per-thread reference counters.
2. Description of the Related Art
In some computer programs, multiple program threads may execute concurrently on a single system and may access shared memory locations, including memory locations that store data representing a shared object, e.g., a shared data structure. In systems that do not include implicit garbage collection, it can be difficult to maintain dynamically allocated memory, given that a shared memory location might be accessible to multiple concurrently executing threads in a dynamic and undetectable manner. Current solutions involve hazard pointers, but these solutions are extremely complex and prone to error. Boehm style collectors have been proposed. However, Boehm collectors suffer from severe limitations and concurrent versions of these collectors are not available.
Reference counting is often used for tracking accessibility of memory locations in concurrent programs to provide information for mechanisms attempting to recycle dynamically allocated memory. A traditional reference counting solution involves associating each location with a “reference counter”, e.g., a shared counter that is incremented by each thread when the thread first accesses the location and is decremented by that thread when it no longer accesses the location. A thread wishing to recycle the location may be able to detect whether it is still accessible simply by reading the associated reference counter.
There are typically two types of operations that a thread can perform on a reference counter. One is an update of the counter value, i.e. an increment or decrement of the counter in response to the thread referencing or dereferencing a shared location. The other is a check to determine whether the value of the reference counter is zero or non-zero. With traditional reference counting mechanisms, incrementing and decrementing the reference counter may need to be performed using a compare-and-swap type operation (e.g., a CAS instruction, or a load-link/store-conditional instruction pair) to maintain coherence of the counters, and such operations may be expensive in terms of latency and/or computational complexity.
As programmers attempt to tailor existing concurrent algorithms for use in highly parallel programs to be executed on multithreaded processors, traditional reference counters may not be sufficient for tracking references to shared locations in the face of increased contention between concurrently executing threads.